#include "Strategy.h"
#include "Frame.h"
#include "Snake.h"
#include "Log.h"
#include <queue>
#include <stdio.h>

using namespace std;

CStrategy::CStrategy(CFrame &cFrame, CSnake &Snake)
    :m_cFrame(cFrame), m_cSnake(Snake)
{
}


CStrategy::~CStrategy()
{
}

EDirType CStrategy::GetDir()
{
    LOG_DBG("GetDir Begin");
    if (!GetNearestFood())
    {
        return EM_DIR_TYPE_ERROR;
    }
    const Pos &stHead = m_cSnake.GetSnakeHead();
    const Pos &stTail = m_cSnake.GetSnakeTail();
    Pos stNextHead;

    //计算广搜下一个方向
    vector<EDirType> vecDir;
    EDirType eDir = EM_DIR_TYPE_ERROR;

    LOG_DBG("Find Food.Head:%d,%d Food:%d,%d", stHead.iX, stHead.iY, m_Food.iX, m_Food.iY);
    GotoPosByBreadthFirstResearch(stHead, m_Food, vecDir);
    if (vecDir.size() <= 0)
    {
        //找不到下个方向，就追尾巴
        LOG_DBG("Follow Tail");
        eDir = FollowTail(stHead);
    }
    else
    {
        //选择远的方向
        eDir = GetFarDir(stHead, vecDir, stTail);
        //计算如果走这个方向还能不能追到尾巴
        stNextHead = GetNextPos(stHead, eDir);
        vector<Pos> vecForecast;
        vecForecast.push_back(stNextHead);

        LOG_DBG("Follow Tail With Forecast.Dir:%d NextHead:%d,%d", eDir, stNextHead.iX, stNextHead.iY);
        if (EM_DIR_TYPE_ERROR == FollowTail(stNextHead,vecForecast))
        {
            //不能追到尾巴，就放弃这个方向，直接去追尾巴
            LOG_DBG("Follow Tail");
            eDir = FollowTail(stHead);
        }

    }

    LOG_DBG("GetDir End.Dir:%d", eDir);
    return eDir;
}

bool CStrategy::CollectFood()
{
    m_Food.iX = 0;
    m_Food.iY = 0;

    const int iHight = m_cFrame.GetMapHight();
    const int iWidth = m_cFrame.GetMapWidth();

    for (int iHightTmp = 0; iHightTmp < iHight; ++iHightTmp)
    {
        for (int iWidthTmp = 0; iWidthTmp < iWidth; ++iWidthTmp)
        {
            const MapUnitData &stMapUnitData = m_cFrame.GetMapUnitData(iWidthTmp, iHightTmp);
            if (stMapUnitData.eType == EM_MAP_UNIT_TYPE_FOOD)
            {
                m_Food.iX = iWidthTmp;
                m_Food.iY = iHightTmp;

                return true;
            }
        }
    }
    return false;
}


bool CStrategy::GetNearestFood()
{
    const Pos &stHeadPos = m_cSnake.GetSnakeHead();

    queue<Pos> qDistanceQueue;
    Pos stTmpPos;

    EMapUnitType(*pTmpMap)[MAX_MAP_WIDTH] = CreateTmpMap();

    qDistanceQueue.push(stHeadPos);
    pTmpMap[stHeadPos.iX][stHeadPos.iY] = EM_MAP_UNIT_TYPE_WALL;


    //for (int iDistanceTmp = 0; iDistanceTmp < iDistance; ++iDistanceTmp)
    while (true)
    {
        int iQueueSize = (int)qDistanceQueue.size();
        if (iQueueSize <= 0)
        {
            break;
        }

        for (int iSizeTmp = 0; iSizeTmp < iQueueSize; ++iSizeTmp)
        {
            stTmpPos = qDistanceQueue.front();
            qDistanceQueue.pop();


            for (int iDir = 0; iDir < 4; ++iDir)
            {
                Pos stDistanceTmpPos = GetNextPos(stTmpPos, (EDirType)iDir);

                EMapUnitType eType = pTmpMap[stDistanceTmpPos.iX][stDistanceTmpPos.iY];

                switch (eType)
                {
                    return true;
                case EM_MAP_UNIT_TYPE_NULL:
                {
                    const MapUnitData & stMapUnitData = m_cFrame.GetMapUnitData(stDistanceTmpPos.iX, stDistanceTmpPos.iY);
                    if (stMapUnitData.eType == EM_MAP_UNIT_TYPE_FOOD)
                    {
                        m_Food = stDistanceTmpPos;
                        return true;
                    }
                    qDistanceQueue.push(stDistanceTmpPos);
                    pTmpMap[stDistanceTmpPos.iX][stDistanceTmpPos.iY] = EM_MAP_UNIT_TYPE_WALL;
                    break;
                }
                default:
                    break;
                }
            }
        }
    }
    return false;
}

EDirType CStrategy::GotoPosByBreadthFirstResearch(const Pos &stSrc, const Pos &stDst, vector<EDirType> &vecDir, const vector<Pos> &vecForecast )
{
    queue<Pos> qBreadthQueue;
    vector<Pos> vecPosLog;
    Pos stTmpPos;

    qBreadthQueue.push(stDst);

    LOG_DBG("Src:%d,%d Dst:%d,%d", stSrc.iX, stSrc.iY, stDst.iX, stDst.iY);

    EMapUnitType(*pTmpMap)[MAX_MAP_WIDTH] = CreateTmpMap(vecForecast);
    while (true)
    {
        int iQueueSize = (int)qBreadthQueue.size();

        if (qBreadthQueue.size() <= 0)
        {
            return EM_DIR_TYPE_ERROR;
        }
        for (int iQueueSizeTmp = 0; iQueueSizeTmp < iQueueSize; ++iQueueSizeTmp)
        {
            if (qBreadthQueue.size() <= 0)
            {
                return EM_DIR_TYPE_ERROR;
            }
            stTmpPos = qBreadthQueue.front();
            qBreadthQueue.pop();

            pTmpMap[stTmpPos.iX][stTmpPos.iY] = EM_MAP_UNIT_TYPE_WALL;

            for (int iDir = 0; iDir < 4; ++iDir)
            {
                Pos stDirTmpPos = GetNextPos(stTmpPos, (EDirType)iDir);

                EMapUnitType eType = pTmpMap[stDirTmpPos.iX][stDirTmpPos.iY];

                switch (eType)
                {
                case EM_MAP_UNIT_TYPE_NULL:
                    qBreadthQueue.push(stDirTmpPos);
                    vecPosLog.push_back(stDirTmpPos);
                    pTmpMap[stDirTmpPos.iX][stDirTmpPos.iY] = EM_MAP_UNIT_TYPE_WALL;
                    break;
                default:
                    break;
                }
                if (stDirTmpPos.iX == stSrc.iX && stDirTmpPos.iY == stSrc.iY)
                {
                    vecDir.push_back(ReverseDir((EDirType)iDir));
                    //return ReverseDir((EDirType)iDir);
                }
            }
        }

        int iVecLogSize = (int)vecPosLog.size();
        string sLogTmp;
        char csLogTmp[16];
        for (int iVecLogSizeTmp = 0; iVecLogSizeTmp < iVecLogSize; ++iVecLogSizeTmp)
        {
            Pos &stTmp = vecPosLog[iVecLogSizeTmp];
            sprintf(csLogTmp, "(%d,%d),", stTmp.iX, stTmp.iY);
            sLogTmp += csLogTmp;
        }
        LOG_DBG("breadth queue:%s",sLogTmp.c_str());
        vecPosLog.clear();
        if (vecDir.size() > 0)
        {
            break;
        }
    }

    return EM_DIR_TYPE_ERROR;
}

EDirType CStrategy::FollowTail(const Pos &stHead, const vector<Pos> &vecForecast )
{
    EDirType eDir = EM_DIR_TYPE_ERROR;
    const Pos &stTail = m_cSnake.GetSnakeTail();

    vector<EDirType> vecDir;
    vector<Pos> vecHeadRound;
    GetRoundPos(stHead, vecHeadRound);
    int iForecastSize = (int)vecForecast.size();

    for (int iRoundSizeTmp = 0; iRoundSizeTmp < (int)vecHeadRound.size(); )
    {
        vecDir.clear();

        const Pos &stHandRoundPos = vecHeadRound[iRoundSizeTmp];
        const MapUnitData &stMapUnitData = m_cFrame.GetMapUnitData(stHandRoundPos.iX, stHandRoundPos.iY);
        if (stMapUnitData.eType == EM_MAP_UNIT_TYPE_FOOD && m_cFrame.IsNear(stHandRoundPos, stTail))
        {
            vecHeadRound.erase(vecHeadRound.begin() + iRoundSizeTmp);
            continue;
        }
        else
        {
            GotoPosByBreadthFirstResearch(stTail, vecHeadRound[iRoundSizeTmp], vecDir, vecForecast);
            if (vecDir.size() <= 0)
            {
                vecHeadRound.erase(vecHeadRound.begin() + iRoundSizeTmp);
                continue;
            }
        }
        ++iRoundSizeTmp;
    }

    int iMaxDistance = 0;
    int iRoundSize = (int)vecHeadRound.size();

    if (iRoundSize <= 0)
    {

        return EM_DIR_TYPE_ERROR;
    }

    Pos stMaxDistancePos = vecHeadRound[0];
   
    for (int iRoundSizeTmp = 0; iRoundSizeTmp < iRoundSize; ++iRoundSizeTmp)
    {
        int iDistanceTmp = GetDistance(vecHeadRound[iRoundSizeTmp], stTail);
        if (iDistanceTmp > iMaxDistance)
        {
            iMaxDistance = iDistanceTmp;
            stMaxDistancePos = vecHeadRound[iRoundSizeTmp];
        }
        else if (iDistanceTmp == iMaxDistance)
        {
            int iFoodDistance = GetDistance(vecHeadRound[iRoundSizeTmp], m_Food);
            int iMaxFoodDistance = GetDistance(stMaxDistancePos, m_Food);
            if (iMaxFoodDistance > iFoodDistance)
            {
                iMaxDistance = iDistanceTmp;
                stMaxDistancePos = vecHeadRound[iRoundSizeTmp];
            }
        }
    }

    eDir = GetNearPosDir(stHead, stMaxDistancePos);

    return eDir;
}

const Pos CStrategy::GetNextPos(const Pos &stPos, EDirType eDir)
{
    Pos stTmpPos = stPos;
    switch (eDir)
    {
    case EM_DIR_TYPE_UP:
        --stTmpPos.iY;
        break;
    case EM_DIR_TYPE_DOWN:
        ++stTmpPos.iY;
        break;
    case EM_DIR_TYPE_LEFT:
        --stTmpPos.iX;
        break;
    case EM_DIR_TYPE_RIGHT:
        ++stTmpPos.iX;
        break;
    default:
        break;
    }
    return stTmpPos;
}

EDirType CStrategy::ReverseDir(EDirType eDir)
{
    switch (eDir)
    {
    case EM_DIR_TYPE_UP:
        return EM_DIR_TYPE_DOWN;
    case EM_DIR_TYPE_DOWN:
        return EM_DIR_TYPE_UP;
    case EM_DIR_TYPE_LEFT:
        return EM_DIR_TYPE_RIGHT;
    case EM_DIR_TYPE_RIGHT:
        return EM_DIR_TYPE_LEFT;
    default:
        break;
    }
    return EM_DIR_TYPE_ERROR;
}

EDirType CStrategy::GetNearPosDir(const Pos &stSrcPos, const Pos &stDesPos)
{
    if (stSrcPos.iX == stDesPos.iX &&  stSrcPos.iY == stDesPos.iY + 1)
    {
        return EM_DIR_TYPE_UP;
    }
    else if (stSrcPos.iX == stDesPos.iX &&  stSrcPos.iY == stDesPos.iY - 1)
    {
        return EM_DIR_TYPE_DOWN;
    }
    else if (stSrcPos.iX - 1 == stDesPos.iX &&  stSrcPos.iY == stDesPos.iY)
    {
        return EM_DIR_TYPE_LEFT;
    }
    else if (stSrcPos.iX + 1 == stDesPos.iX &&  stSrcPos.iY == stDesPos.iY)
    {
        return EM_DIR_TYPE_RIGHT;
    }
    return EM_DIR_TYPE_ERROR;
}

void CStrategy::GetRoundPos(const Pos &stSrcPos, vector<Pos> &vecRoundPos, const int iDistance)
{
    queue<Pos> qDistanceQueue;
    Pos stTmpPos;

    qDistanceQueue.push(stSrcPos);

    EMapUnitType(*pTmpMap)[MAX_MAP_WIDTH] = CreateTmpMap();

    for (int iDistanceTmp = 0; iDistanceTmp < iDistance; ++iDistanceTmp)
    {
        int iQueueSize = (int)qDistanceQueue.size();
        for (int iSizeTmp = 0; iSizeTmp < iQueueSize; ++iSizeTmp)
        {
            stTmpPos = qDistanceQueue.front();
            qDistanceQueue.pop();

            pTmpMap[stTmpPos.iX][stTmpPos.iY] = EM_MAP_UNIT_TYPE_WALL;

            for (int iDir = 0; iDir < 4; ++iDir)
            {
                Pos stDistanceTmpPos = GetNextPos(stTmpPos, (EDirType)iDir);

                EMapUnitType eType = pTmpMap[stDistanceTmpPos.iX][stDistanceTmpPos.iY];

                switch (eType)
                {
                case EM_MAP_UNIT_TYPE_NULL:
                    if (iDistanceTmp == iDistance - 1)
                    {
                        vecRoundPos.push_back(stDistanceTmpPos);
                    }
                    else
                    {
                        qDistanceQueue.push(stDistanceTmpPos);
                    }
                    pTmpMap[stDistanceTmpPos.iX][stDistanceTmpPos.iY] = EM_MAP_UNIT_TYPE_WALL;
                    break;
                default:
                    break;
                }
            }
        }
    }
}

int CStrategy::GetDistance(const Pos &stSrcPos, const Pos &stDesPos)
{
    int iDistance = 0;
    int iDistanceX = 0;
    int iDistanceY = 0;

    iDistanceX = stSrcPos.iX - stDesPos.iX;
    if (iDistanceX < 0)
    {
        iDistance -= iDistanceX;
    }
    else
    {
        iDistance += iDistanceX;
    }
    iDistanceY = stSrcPos.iY - stDesPos.iY;
    if (iDistanceY < 0)
    {
        iDistance -= iDistanceY;
    }
    else
    {
        iDistance += iDistanceY;
    }

    return iDistance;
}

EDirType CStrategy::GetFarDir(const Pos &stSrcPos, const vector<EDirType> &vecSrcDir, const Pos &stDesPos)
{
    int iMaxDistance = 0;
    EDirType iMaxDistanceDir = EM_DIR_TYPE_ERROR;

    int iDirSize = (int)vecSrcDir.size();
    Pos stDirPos;


    for (int iDirSizeTmp = 0; iDirSizeTmp < iDirSize; ++iDirSizeTmp)
    {
        stDirPos = GetNextPos(stSrcPos, vecSrcDir[iDirSizeTmp]);

        int iDistanceTmp = GetDistance(stDirPos, stDesPos);
        if (iDistanceTmp > iMaxDistance)
        {
            iMaxDistance = iDistanceTmp;
            iMaxDistanceDir = vecSrcDir[iDirSizeTmp];
        }
    }
    return iMaxDistanceDir;
}

EDirType CStrategy::GetNearDir(const Pos &stSrcPos, const vector<EDirType> &vecSrcDir, const Pos &stDesPos)
{
    int iMinDistance = MAX_MAP_HIGHT + MAX_MAP_WIDTH;
    EDirType iMinDistanceDir = EM_DIR_TYPE_ERROR;

    int iDirSize = (int)vecSrcDir.size();
    Pos stDirPos;

    for (int iDirSizeTmp = 0; iDirSizeTmp < iDirSize; ++iDirSize)
    {
        stDirPos = GetNextPos(stSrcPos, vecSrcDir[iDirSizeTmp]);

        int iDistanceTmp = GetDistance(stDirPos, stDesPos);
        if (iDistanceTmp < iMinDistance)
        {
            iMinDistance = iDistanceTmp;
            iMinDistanceDir = vecSrcDir[iDirSizeTmp];
        }
    }
    return iMinDistanceDir;
}

EMapUnitType(*CStrategy::CreateTmpMap(const vector<Pos> &vecForecast))[MAX_MAP_WIDTH]
{
    static EMapUnitType iTmpMap[MAX_MAP_HIGHT][MAX_MAP_WIDTH];

    int iHight = m_cFrame.GetMapHight();
    int iWidth = m_cFrame.GetMapWidth();

    int iForcastSize = (int)vecForecast.size();

    const Pos *pSnake = m_cSnake.GetSnake();
    const int iSnakeLength = m_cSnake.GetSnakeLength();

    int iFoodCount = 0;

    for (int iForcastSizeTmp = 0; iForcastSizeTmp < iForcastSize; ++iForcastSizeTmp)
    {
        const Pos &stForcastPos = vecForecast[iForcastSizeTmp];
        const MapUnitData &stMapUnitData = m_cFrame.GetMapUnitData(stForcastPos.iX, stForcastPos.iY);

        if (stMapUnitData.eType == EM_MAP_UNIT_TYPE_FOOD)
        {
            ++iFoodCount;
        }
    }

    for (int iHightTmp = 0; iHightTmp < iHight; ++iHightTmp)
    {
        for (int iWidthTmp = 0;iWidthTmp < iWidth; ++iWidthTmp)
        {
            const MapUnitData &stMapUnitData = m_cFrame.GetMapUnitData(iWidthTmp, iHightTmp);

            switch (stMapUnitData.eType)
            {
            case EM_MAP_UNIT_TYPE_NULL:
            case EM_MAP_UNIT_TYPE_FOOD:
                iTmpMap[iWidthTmp][iHightTmp] = EM_MAP_UNIT_TYPE_NULL;
                for (int iIndex = 0; iIndex < iForcastSize; ++iIndex)
                {
                    const Pos &stTmpPos = vecForecast[iIndex];
                    if (stTmpPos.iX == iWidthTmp && stTmpPos.iY == iHightTmp)
                    {
                        iTmpMap[iWidthTmp][iHightTmp] = EM_MAP_UNIT_TYPE_WALL;
                    }
                }
                break;
            case EM_MAP_UNIT_TYPE_WALL:
                iTmpMap[iWidthTmp][iHightTmp] = EM_MAP_UNIT_TYPE_WALL;
            case EM_MAP_UNIT_TYPE_SNACKE:
                if (iForcastSize >= iSnakeLength)
                {
                    iTmpMap[iWidthTmp][iHightTmp] = EM_MAP_UNIT_TYPE_NULL;
                }
                else
                {
                    iTmpMap[iWidthTmp][iHightTmp] = EM_MAP_UNIT_TYPE_WALL;
//                     for (int iSnakeIndex = 0; iSnakeIndex < iSnakeLength; ++iSnakeIndex)
//                     {
//                         const Pos &stTmpPos = pSnake[iSnakeIndex];
//                         if (stTmpPos.iX == iWidthTmp && stTmpPos.iY == iHightTmp)
//                         {
//                             if (iSnakeLength - iForcastSize + iFoodCount <= iSnakeIndex)
//                             {
//                                 iTmpMap[iWidthTmp][iHightTmp] = EM_MAP_UNIT_TYPE_NULL;
//                             }
//                         }
//                     }
                }
            default:
                break;
            }
        }
    }

    string sLine;
    char buff[16];
    for (int iHightTmp = 0; iHightTmp < iHight; ++iHightTmp)
    {
        sLine.clear();
        for (int iWidthTmp = 0;iWidthTmp < iWidth; ++iWidthTmp)
        {
            sprintf(buff, "%d,", (int)iTmpMap[iWidthTmp][iHightTmp]);
            sLine += buff;
        }
        LOG_DBG("TmpMap:%d:%s", iHightTmp, sLine.c_str());
    }

    return iTmpMap;
}
